import sys
import re

class Apriori:
    """ 
    A very basic Apriori Algorithm   
    
    datasets -> data sets
    min_sup -> mini support
    min_conf -> mini confidence
    """
    def __init__(self, datasets, min_sup, min_conf):
        self.dataset = datasets
        self.min_sup = min_sup
        self.min_conf = min_conf
        self.L = {}
        self.max_r = 0;
        self.SRules = {}
        self.total = 0
        self.readdata()
        self.support = {}


    def readdata(self):
        f = open(self.dataset, "r")
    
        mydss = []
        for l in f.readlines(): 
            s = []
            self.total += 1
            for d in re.split("\s", l):
                if d != '':
                    s += [int(d)]                
            mydss += [s]
        #print self.total
        #print mydss
        self.dss = mydss


    def GenL0(self):
        
        # first, Get C0
        self.L[0] = {}
        for ds in self.dss:
            for d in ds:
                if not self.L[0].has_key(tuple([d])):
                    self.L[0][tuple([d])] = 1
                else:
                    self.L[0][tuple([d])] += 1 
        #print "C0:", self.L[0]
        
        # seconf, Get L0
        tmp = []
        for (k, v) in self.L[0].items():
            if (v * 100) < (self.min_sup  * self.total):
                tmp += [k]
                
        #print tmp
        for delitem in tmp:
            self.L[0].__delitem__(delitem)
                
        #print "L0:", self.L[0]
        
    def GenNewKeys(self, keys):
        if keys == [] or (not keys[0]):
            return
        l = len(keys[0]) + 1
        new_keys = {}
        for p in keys:
            for q in keys:
                sp = set(p)
                sq = set(q)
                spql = list(sp | sq)
                spql.sort()
                spq = tuple(spql)
                #print spq
                #print sp, sq, spq
                if l == len(spq):
                    new_keys[tuple(spq)] = 0
                    
        return new_keys
                    
    def IterationL(self):
        self.GenL0()
        if self.L[0] == {}:
            return self.L
        
        r = 0
        while True:
            r = r + 1
            self.L[r] = self.GenNewKeys(self.L[r - 1].keys())
            for (k, v) in self.L[r].items():
                for ds in self.dss:

                    if set(k).issubset(set(ds)):
                        self.L[r][k] += 1
                                
            tmp = []
            for (k, v) in self.L[r].items():
                if (v * 100) < (self.min_sup  * self.total):
                    tmp += [k]
                    
            for delitem in tmp:
                self.L[r].__delitem__(delitem)
            
            if self.L[r] == {}:
                #print "Iteration End"
                self.max_r = r;
                return self.L
        
        return self.L
    def GenAllRules(self): 
        self.SRules = {}
        if self.L[0] == {}: return
        #for r in range(1, self.max_r):
        #print self.L[r]
        for (k, v) in self.L[self.max_r - 1].items():
            self.GenRules(k, k, self.max_r - 1) 
                
    def GenRules(self, l, x, r):
        #print l, x
        if r < 1 : return
        for i in x:
            xs = list(set(x) - set([i]))
            xs.sort()
            xs = tuple(xs)
            
            conf =  100 * self.getSupport(l, len(l) - 1) / self.getSupport(xs, len(xs) - 1)
            
            if conf >= self.min_conf:
                #print l, self.getSupport(l, r),"/",
                #print xs, self.getSupport(xs, r - 1),"->",
                
                self.SRules[tuple((xs,tuple(set(l) - set(xs))))] = conf
                #print xs, "->", tuple(set(l) - set(xs)), "==",
                #print conf
                
            self.GenRules(l, xs, len(xs) - 1)
        
        
    def getSupport(self, x, r):
        return self.L[r][tuple(x)]

    def AprioriMine(self):
        fsets = self.IterationL().values()
    
        """
        print "Minimal Support:", min_sup        print "Minimal Confidence:%d%%" % min_conf
        print
        print "Frequent Itemsets:"
        """
        for i in fsets:
            for (j, k) in i.items():
                tmp = k * 100 / self.total
                self.support[j] = tmp
                #print j, "->", tmp,"%;", 
            #print
        
        self.GenAllRules()
        #print "\n\n-----------------"
        #print self.support
        
        #print "Strong Rules:"
        
        tup5 = []
        for (k, v) in self.SRules.items():
            a = list(k[0])
            a.sort()
            a = tuple(a)
            b = list(k[1])
            b.sort()
            b = tuple(b)
            tup5 += [(v, k[0], k[1], self.support[a] , self.support[b] )]
            #print k[0],"->",k[1],":",v,"% [(", k[0],":", self.support[a], "% ), ( ", k[1],":",self.support[b], "% )]" 

        tup5.sort()
        #for i in tup5:
            #print i        return tup5

"""
if __name__ == "__main__":
    if len(sys.argv) > 3:
        filename = sys.argv[1]
        min_sup = int(sys.argv[2])
        min_conf = int(sys.argv[3])
    else:
        print "format: apriori.py DataSetsFile MinSupPersent MinConfPersent "
        exit(0)
                
        
    ap = Apriori(filename, min_sup, min_conf)
    
    ap.AprioriMine()
"""
